home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland C++ V5.02 / TEMPLDEF.PAK / MAP_S.CTT < prev    next >
Text File  |  1997-05-06  |  14KB  |  548 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // class CMapStringTo - a mapping from CStrings to 'VALUE's.
  3. // passed in parameters as ARG_TYPE
  4. //
  5. // optional definitions:
  6. //  IS_SERIAL   - enable serialization through CArchive extraction & insertion
  7. //  HAS_CREATE  - call constructors and destructors
  8. //
  9. // This is a part of the Microsoft Foundation Classes C++ library.
  10. // Copyright (C) 1992 Microsoft Corporation
  11. // All rights reserved.
  12. //
  13. // This source code is only intended as a supplement to the
  14. // Microsoft Foundation Classes Reference and related
  15. // electronic documentation provided with the library.
  16. // See these sources for detailed information regarding the
  17. // Microsoft Foundation Classes product.
  18. /////////////////////////////////////////////////////////////////////////////
  19.  
  20. //$DECLARE_TEMPLATE
  21. /////////////////////////////////////////////////////////////////////////////
  22. template<class VALUE, class ARG_VALUE>
  23. class CMapStringTo : public CObject
  24. {
  25. $ifdef IS_SERIAL
  26.     DECLARE_SERIAL(CMapStringTo)
  27. $else
  28.     DECLARE_DYNAMIC(CMapStringTo)
  29. $endif //!IS_SERIAL
  30. protected:
  31.     // Association
  32.     struct CAssoc
  33.     {
  34.         CAssoc* pNext;
  35.         UINT nHashValue;  // needed for efficient iteration
  36.         CString key;
  37.         VALUE value;
  38.     };
  39.  
  40. public:
  41.  
  42. // Construction
  43.     CMapStringTo(int nBlockSize = 10);
  44.  
  45. // Attributes
  46.     // number of elements
  47.     int GetCount() const;
  48.     BOOL IsEmpty() const;
  49.  
  50.     // Lookup
  51.     BOOL Lookup(LPCTSTR key, VALUE& rValue) const;
  52.     BOOL LookupKey(LPCTSTR key, LPCTSTR& rKey) const;
  53.  
  54. // Operations
  55.     // Lookup and add if not there
  56.     VALUE& operator[](LPCTSTR key);
  57.  
  58.     // add a new (key, value) pair
  59.     void SetAt(LPCTSTR key, ARG_VALUE newValue);
  60.  
  61.     // removing existing (key, ?) pair
  62.     BOOL RemoveKey(LPCTSTR key);
  63.     void RemoveAll();
  64.  
  65.     // iterating all (key, value) pairs
  66.     POSITION GetStartPosition() const;
  67.     void GetNextAssoc(POSITION& rNextPosition, CString& rKey, VALUE& rValue) const;
  68.  
  69.     // advanced features for derived classes
  70.     UINT GetHashTableSize() const;
  71.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  72.  
  73. // Overridables: special non-virtual (see map implementation for details)
  74.     // Routine used to user-provided hash keys
  75.     UINT HashKey(LPCTSTR key) const;
  76.  
  77. // Implementation
  78. protected:
  79.     CAssoc** m_pHashTable;
  80.     UINT m_nHashTableSize;
  81.     int m_nCount;
  82.     CAssoc* m_pFreeList;
  83.     struct CPlex* m_pBlocks;
  84.     int m_nBlockSize;
  85.  
  86.     CAssoc* NewAssoc();
  87.     void FreeAssoc(CAssoc*);
  88.     CAssoc* GetAssocAt(LPCTSTR, UINT&) const;
  89.  
  90. public:
  91.     ~CMapStringTo();
  92. $ifdef IS_SERIAL
  93.     void Serialize(CArchive&);
  94. $endif //IS_SERIAL
  95. #ifdef _DEBUG
  96.     void Dump(CDumpContext&) const;
  97.     void AssertValid() const;
  98. #endif
  99.  
  100. protected:
  101.     // local typedefs for CTypedPtrMap class template
  102.     typedef CString BASE_KEY;
  103.     typedef LPCTSTR BASE_ARG_KEY;
  104.     typedef VALUE BASE_VALUE;
  105.     typedef ARG_VALUE BASE_ARG_VALUE;
  106. };
  107.  
  108. //$IMPLEMENT_TEMPLATE_INLINES
  109. ////////////////////////////////////////////////////////////////////////////
  110. template<class VALUE, class ARG_VALUE>
  111. _AFXCOLL_INLINE int CMapStringTo<VALUE, ARG_VALUE>::GetCount() const
  112.     { return m_nCount; }
  113. template<class VALUE, class ARG_VALUE>
  114. _AFXCOLL_INLINE BOOL CMapStringTo<VALUE, ARG_VALUE>::IsEmpty() const
  115.     { return m_nCount == 0; }
  116. template<class VALUE, class ARG_VALUE>
  117. _AFXCOLL_INLINE void CMapStringTo<VALUE, ARG_VALUE>::SetAt(LPCTSTR key, ARG_VALUE newValue)
  118.     { (*this)[key] = newValue; }
  119. template<class VALUE, class ARG_VALUE>
  120. _AFXCOLL_INLINE POSITION CMapStringTo<VALUE, ARG_VALUE>::GetStartPosition() const
  121.     { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
  122. template<class VALUE, class ARG_VALUE>
  123. _AFXCOLL_INLINE UINT CMapStringTo<VALUE, ARG_VALUE>::GetHashTableSize() const
  124.     { return m_nHashTableSize; }
  125.  
  126. //$IMPLEMENT_TEMPLATE
  127. // This is a part of the Microsoft Foundation Classes C++ library.
  128. // Copyright (C) 1992-1995 Microsoft Corporation
  129. // All rights reserved.
  130. //
  131. // This source code is only intended as a supplement to the
  132. // Microsoft Foundation Classes Reference and related
  133. // electronic documentation provided with the library.
  134. // See these sources for detailed information regarding the
  135. // Microsoft Foundation Classes product.
  136.  
  137. /////////////////////////////////////////////////////////////////////////////
  138. //
  139. // Implementation of parmeterized Map from CString to value
  140. //
  141. /////////////////////////////////////////////////////////////////////////////
  142.  
  143. #include "stdafx.h"
  144.  
  145. #ifdef AFX_COLL2_SEG
  146. #pragma code_seg(AFX_COLL2_SEG)
  147. #endif
  148.  
  149. #ifdef _DEBUG
  150. #undef THIS_FILE
  151. static char THIS_FILE[] = __FILE__;
  152. #endif
  153.  
  154. $ifdef HAS_CREATE
  155. #include "elements.h"  // used for special creation
  156. $endif
  157.  
  158. #define new DEBUG_NEW
  159.  
  160. /////////////////////////////////////////////////////////////////////////////
  161.  
  162. template<class VALUE, class ARG_VALUE>
  163. CMapStringTo<VALUE, ARG_VALUE>::CMapStringTo(int nBlockSize)
  164. {
  165.     ASSERT(nBlockSize > 0);
  166.  
  167.     m_pHashTable = NULL;
  168.     m_nHashTableSize = 17;  // default size
  169.     m_nCount = 0;
  170.     m_pFreeList = NULL;
  171.     m_pBlocks = NULL;
  172.     m_nBlockSize = nBlockSize;
  173. }
  174.  
  175. template<class VALUE, class ARG_VALUE>
  176. inline UINT CMapStringTo<VALUE, ARG_VALUE>::HashKey(LPCTSTR key) const
  177. {
  178.     UINT nHash = 0;
  179.     while (*key)
  180.         nHash = (nHash<<5) + nHash + *key++;
  181.     return nHash;
  182. }
  183.  
  184. template<class VALUE, class ARG_VALUE>
  185. void CMapStringTo<VALUE, ARG_VALUE>::InitHashTable(
  186.     UINT nHashSize, BOOL bAllocNow)
  187. //
  188. // Used to force allocation of a hash table or to override the default
  189. //   hash table size of (which is fairly small)
  190. {
  191.     ASSERT_VALID(this);
  192.     ASSERT(m_nCount == 0);
  193.     ASSERT(nHashSize > 0);
  194.  
  195.     if (m_pHashTable != NULL)
  196.     {
  197.         // free hash table
  198.         delete[] m_pHashTable;
  199.         m_pHashTable = NULL;
  200.     }
  201.  
  202.     if (bAllocNow)
  203.     {
  204.         m_pHashTable = new CAssoc* [nHashSize];
  205.         memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  206.     }
  207.     m_nHashTableSize = nHashSize;
  208. }
  209.  
  210. template<class VALUE, class ARG_VALUE>
  211. void CMapStringTo<VALUE, ARG_VALUE>::RemoveAll()
  212. {
  213.     ASSERT_VALID(this);
  214.  
  215.     if (m_pHashTable != NULL)
  216.     {
  217.         // destroy elements
  218.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  219.         {
  220.             CAssoc* pAssoc;
  221.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  222.               pAssoc = pAssoc->pNext)
  223.             {
  224.                 pAssoc->key.Empty();  // free up string data
  225. $ifdef HAS_CREATE
  226.                 DestructElement(&pAssoc->value);
  227. $endif
  228.             }
  229.         }
  230.  
  231.         // free hash table
  232.         delete [] m_pHashTable;
  233.         m_pHashTable = NULL;
  234.     }
  235.  
  236.     m_nCount = 0;
  237.     m_pFreeList = NULL;
  238.     m_pBlocks->FreeDataChain();
  239.     m_pBlocks = NULL;
  240. }
  241.  
  242. template<class VALUE, class ARG_VALUE>
  243. CMapStringTo<VALUE, ARG_VALUE>::~CMapStringTo()
  244. {
  245.     RemoveAll();
  246.     ASSERT(m_nCount == 0);
  247. }
  248.  
  249. /////////////////////////////////////////////////////////////////////////////
  250. // Assoc helpers
  251. // same as CList implementation except we store CAssoc's not CNode's
  252. //    and CAssoc's are singly linked all the time
  253.  
  254. template<class VALUE, class ARG_VALUE>
  255. CMapStringTo<VALUE, ARG_VALUE>::CAssoc*
  256. CMapStringTo<VALUE, ARG_VALUE>::NewAssoc()
  257. {
  258.     if (m_pFreeList == NULL)
  259.     {
  260.         // add another block
  261.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  262.                             sizeof(CMapStringTo::CAssoc));
  263.         // chain them into free list
  264.         CMapStringTo::CAssoc* pAssoc =
  265.                 (CMapStringTo::CAssoc*) newBlock->data();
  266.         // free in reverse order to make it easier to debug
  267.         pAssoc += m_nBlockSize - 1;
  268.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  269.         {
  270.             pAssoc->pNext = m_pFreeList;
  271.             m_pFreeList = pAssoc;
  272.         }
  273.     }
  274.     ASSERT(m_pFreeList != NULL);  // we must have something
  275.  
  276.     CMapStringTo::CAssoc* pAssoc = m_pFreeList;
  277.     m_pFreeList = m_pFreeList->pNext;
  278.     m_nCount++;
  279.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  280.     memcpy(&pAssoc->key, &afxEmptyString, sizeof(CString));
  281. $ifdef HAS_CREATE
  282.     ConstructElement(&pAssoc->value);
  283. $endif
  284. $ifdef USE_MEMSET
  285.     memset(&pAssoc->value, 0, sizeof(VALUE));
  286. $endif
  287. $ifdef USE_ASSIGN
  288.     pAssoc->value = 0;
  289. $endif
  290.     return pAssoc;
  291. }
  292.  
  293. template<class VALUE, class ARG_VALUE>
  294. void CMapStringTo<VALUE, ARG_VALUE>::FreeAssoc(CMapStringTo::CAssoc* pAssoc)
  295. {
  296.     pAssoc->key.Empty();  // free up string data
  297. $ifdef HAS_CREATE
  298.     DestructElement(&pAssoc->value);
  299. $endif
  300.     pAssoc->pNext = m_pFreeList;
  301.     m_pFreeList = pAssoc;
  302.     m_nCount--;
  303.     ASSERT(m_nCount >= 0);    // make sure we don't underflow
  304.  
  305.     // if no more elements, cleanup completely
  306.     if (m_nCount == 0)
  307.         RemoveAll();
  308. }
  309.  
  310. template<class VALUE, class ARG_VALUE>
  311. CMapStringTo<VALUE, ARG_VALUE>::CAssoc*
  312. CMapStringTo<VALUE, ARG_VALUE>::GetAssocAt(LPCTSTR key, UINT& nHash) const
  313. // find association (or return NULL)
  314. {
  315.     nHash = HashKey(key) % m_nHashTableSize;
  316.  
  317.     if (m_pHashTable == NULL)
  318.         return NULL;
  319.  
  320.     // see if it exists
  321.     CAssoc* pAssoc;
  322.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  323.     {
  324.         if (pAssoc->key == key)
  325.             return pAssoc;
  326.     }
  327.     return NULL;
  328. }
  329.  
  330. /////////////////////////////////////////////////////////////////////////////
  331.  
  332. template<class VALUE, class ARG_VALUE>
  333. BOOL CMapStringTo<VALUE, ARG_VALUE>::Lookup(LPCTSTR key, VALUE& rValue) const
  334. {
  335.     ASSERT_VALID(this);
  336.  
  337.     UINT nHash;
  338.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  339.     if (pAssoc == NULL)
  340.         return FALSE;  // not in map
  341.  
  342.     rValue = pAssoc->value;
  343.     return TRUE;
  344. }
  345.  
  346. template<class VALUE, class ARG_VALUE>
  347. BOOL CMapStringTo<VALUE, ARG_VALUE>::LookupKey(LPCTSTR key, LPCTSTR& rKey) const
  348. {
  349.     ASSERT_VALID(this);
  350.  
  351.     UINT nHash;
  352.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  353.     if (pAssoc == NULL)
  354.         return FALSE;  // not in map
  355.  
  356.     rKey = pAssoc->key;
  357.     return TRUE;
  358. }
  359.  
  360. template<class VALUE, class ARG_VALUE>
  361. VALUE& CMapStringTo<VALUE, ARG_VALUE>::operator[](LPCTSTR key)
  362. {
  363.     ASSERT_VALID(this);
  364.  
  365.     UINT nHash;
  366.     CAssoc* pAssoc;
  367.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  368.     {
  369.         if (m_pHashTable == NULL)
  370.             InitHashTable(m_nHashTableSize);
  371.  
  372.         // it doesn't exist, add a new Association
  373.         pAssoc = NewAssoc();
  374.         pAssoc->nHashValue = nHash;
  375.         pAssoc->key = key;
  376.         // 'pAssoc->value' is a constructed object, nothing more
  377.  
  378.         // put into hash table
  379.         pAssoc->pNext = m_pHashTable[nHash];
  380.         m_pHashTable[nHash] = pAssoc;
  381.     }
  382.     return pAssoc->value;  // return new reference
  383. }
  384.  
  385.  
  386. template<class VALUE, class ARG_VALUE>
  387. BOOL CMapStringTo<VALUE, ARG_VALUE>::RemoveKey(LPCTSTR key)
  388. // remove key - return TRUE if removed
  389. {
  390.     ASSERT_VALID(this);
  391.  
  392.     if (m_pHashTable == NULL)
  393.         return FALSE;  // nothing in the table
  394.  
  395.     CAssoc** ppAssocPrev;
  396.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  397.  
  398.     CAssoc* pAssoc;
  399.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  400.     {
  401.         if (pAssoc->key == key)
  402.         {
  403.             // remove it
  404.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  405.             FreeAssoc(pAssoc);
  406.             return TRUE;
  407.         }
  408.         ppAssocPrev = &pAssoc->pNext;
  409.     }
  410.     return FALSE;  // not found
  411. }
  412.  
  413.  
  414. /////////////////////////////////////////////////////////////////////////////
  415. // Iterating
  416.  
  417. template<class VALUE, class ARG_VALUE>
  418. void CMapStringTo<VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
  419.     CString& rKey, VALUE& rValue) const
  420. {
  421.     ASSERT_VALID(this);
  422.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  423.  
  424.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  425.     ASSERT(pAssocRet != NULL);
  426.  
  427.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  428.     {
  429.         // find the first association
  430.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  431.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  432.                 break;
  433.         ASSERT(pAssocRet != NULL);  // must find something
  434.     }
  435.  
  436.     // find next association
  437.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  438.     CAssoc* pAssocNext;
  439.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  440.     {
  441.         // go to next bucket
  442.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  443.           nBucket < m_nHashTableSize; nBucket++)
  444.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  445.                 break;
  446.     }
  447.  
  448.     rNextPosition = (POSITION) pAssocNext;
  449.  
  450.     // fill in return data
  451.     rKey = pAssocRet->key;
  452.     rValue = pAssocRet->value;
  453. }
  454.  
  455. $ifdef IS_SERIAL
  456. /////////////////////////////////////////////////////////////////////////////
  457. // Serialization
  458.  
  459. template<class VALUE, class ARG_VALUE>
  460. void CMapStringTo<VALUE, ARG_VALUE>::Serialize(CArchive& ar)
  461. {
  462.     ASSERT_VALID(this);
  463.  
  464.     CObject::Serialize(ar);
  465.  
  466.     if (ar.IsStoring())
  467.     {
  468.         ar.WriteCount(m_nCount);
  469.         if (m_nCount == 0)
  470.             return;  // nothing more to do
  471.  
  472.         ASSERT(m_pHashTable != NULL);
  473.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  474.         {
  475.             CAssoc* pAssoc;
  476.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  477.               pAssoc = pAssoc->pNext)
  478.             {
  479.                 ar << pAssoc->key;
  480.                 ar << pAssoc->value;
  481.             }
  482.         }
  483.     }
  484.     else
  485.     {
  486.         DWORD nNewCount = ar.ReadCount();
  487.         CString newKey;
  488.         VALUE newValue;
  489.         while (nNewCount--)
  490.         {
  491.             ar >> newKey;
  492.             ar >> newValue;
  493.             SetAt(newKey, newValue);
  494.         }
  495.     }
  496. }
  497. $endif //IS_SERIAL
  498.  
  499. /////////////////////////////////////////////////////////////////////////////
  500. // Diagnostics
  501.  
  502. #ifdef _DEBUG
  503. template<class VALUE, class ARG_VALUE>
  504. void CMapStringTo<VALUE, ARG_VALUE>::Dump(CDumpContext& dc) const
  505. {
  506.     CObject::Dump(dc);
  507.  
  508.     dc << "with " << m_nCount << " elements";
  509.     if (dc.GetDepth() > 0)
  510.     {
  511.         // Dump in format "[key] -> value"
  512.         CString key;
  513.         VALUE val;
  514.  
  515.         POSITION pos = GetStartPosition();
  516.         while (pos != NULL)
  517.         {
  518.             GetNextAssoc(pos, key, val);
  519.             dc << "\n\t[" << key << "] = " << val;
  520.         }
  521.     }
  522.  
  523.     dc << "\n";
  524. }
  525.  
  526. template<class VALUE, class ARG_VALUE>
  527. void CMapStringTo<VALUE, ARG_VALUE>::AssertValid() const
  528. {
  529.     CObject::AssertValid();
  530.  
  531.     ASSERT(m_nHashTableSize > 0);
  532.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  533.         // non-empty map should have hash table
  534. }
  535. #endif //_DEBUG
  536.  
  537. #ifdef AFX_INIT_SEG
  538. #pragma code_seg(AFX_INIT_SEG)
  539. #endif
  540.  
  541. $ifdef IS_SERIAL
  542. IMPLEMENT_SERIAL(CMapStringTo, CObject, 0)
  543. $else
  544. IMPLEMENT_DYNAMIC(CMapStringTo, CObject)
  545. $endif //!IS_SERIAL
  546.  
  547. /////////////////////////////////////////////////////////////////////////////
  548.